In many computer systems, it is quite common to represent and convey information to a user through digital images. These images may take a variety of forms, such as for example, alphanumeric characters, cartesian graphs, and other pictorial representations. In many applications, the digital images are conveyed to a user on a display device, such as a raster scan video monitor, printer or the like. Typically, the images to be displayed are stored in digital form, manipulated, and then displayed.
Parametric curves and curved surfaces are common functions which are used in the computer generation of surfaces and objects on a display such as, for example, in mechanical computer aided design ("CAD") applications. Since high speed hardware capable of rendering vectors and polygons is known in the prior art, high speed rendering of curved lines and curved surfaces is usually done by subdividing and rendering them on a CRT as a plurality of straight-lines or planar polygons. (For a more thorough understanding of prior art methods for rendering curves and/or surfaces, see: Bishop, G. and Weimer, D., "Fast Phong Shading" pp 103-106 Computer Graphics Vol. 20, Number 4, August, 1986; Foley, J. D. and Van Dam, A., 1983 Fundamentals of Interactive Computer Graphics, Addison Wesley, Reading, MA.; Gouraud, H., June 1971. "Continuous Shading of Curved Surfaces." IEEE Transactions on Computers, Vol. 20, No. 6, pp 623-628; Swanson, R. and Thayer, L., "A Fast Shaded-Polygon Renderer," Computer Graphics, Vol. 20, No. 4, pp 95-101, August, 1986.).
However, with respect to the rendering of higher order curves and surfaces, prior art systems employ recursive subdivision methods which are expensive to implement in computer hardware because of the high speed stack memory requirements.
The present invention employs an adaptive forward difference ("AFD") technique which overcomes the problems associated with the prior art, yet requires relatively simple and inexpensive circuitry using ordinary forward differencing (advancing along a parametric curve or surface in constant parameter increments), as well as a new adaptive method superior to prior art adaptive subdivision methods of recursively dividing the object until the resulting pieces are smaller than one pixel. The present invention adapts the forward difference parameter increment so as to advance along the curve or surface with a step size (i.e., the distance between the previously drawn pixel location and the current pixel location of the curve or surface being rendered) which is approximately equal to the distance between two adjacent pixels (hereinafter referred to as a "single or one pixel increment"). This adaptation is performed by transforming the equation of the curve to an identical curve with different parameterization, such that the step size is increased or decreased such that the curve proceeds in substantially uniform increments from one pixel to the next. AFD differs from prior art recursive subdivision methods for rendering curves because it does not require manipulation of the complex prior art stack memory circuitry and therefore is simpler and more efficient. Further, the rendering of the curve, curved surface or object yielded by the present invention is more accurate than it would otherwise be if rendered by the prior art ordinary forward differencing method with piece-wise, straight-line or planar polygon approximation.